Programmer Plus 2007/Programmer-Plus-2007.iso/Programming/Report Writers/Crystal Repot 9.0 Full CD version/Setup.exe/SRC/HOARDDLL.ZIP/3rdParty/hoard/libhoard-2.0.2/heap.h

C/C++ Source or Header | 2002-06-18 | 16.8 KB | 616 lines

///-*-C++-*-//////////////////////////////////////////////////////////////////
//
// Hoard: A Fast, Scalable, and Memory-Efficient Allocator
//        for Shared-Memory Multiprocessors
// Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
//
// Copyright (c) 1998-2000, The University of Texas at Austin.
//
// This library is free software; you can redistribute it and/or modify
// it under the terms of the GNU Library General Public License as
// published by the Free Software Foundation, http://www.fsf.org.
//
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Library General Public License for more details.
//
//////////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////////
//
// Note: This file was modified by Crystal Decisions in June 2002.
//
//////////////////////////////////////////////////////////////////////////////


/*
  heap.h
  ------------------------------------------------------------------------
  hoardHeap, the base class for threadHeap and processHeap.
  ------------------------------------------------------------------------
  @(#) $Id: heap.h,v 1.67 2000/03/27 21:55:27 emery Exp $
  ------------------------------------------------------------------------
  Emery Berger                    | <http://www.cs.utexas.edu/users/emery>
  Department of Computer Sciences |             <http://www.cs.utexas.edu>
  University of Texas at Austin   |                <http://www.utexas.edu>
  ========================================================================
*/


#ifndef _HEAP_H_
#define _HEAP_H_

#include "config.h"

#include <assert.h>
#include <math.h>

#include "arch-specific.h"
#include "superblock.h"
#include "heapstats.h"

class processHeap; // forward declaration


class hoardHeap {

public:

  hoardHeap (void);

#if !defined(CRYSTAL_HOARD)
  // A superblock that holds more than one object must hold at least
  // this many bytes.
  enum { SUPERBLOCK_SIZE = 8192 };
#else
  // Superblocks are grouped into different classes, rather than a
  // single class of size SUPERBLOCK_SIZE.
  #ifdef WIN32
  enum { SUPERBLOCK_CLASSES = 1 };
  #else
  enum { SUPERBLOCK_CLASSES = 3 };
  #endif
#endif

  // A thread heap must be at least 1/EMPTY_FRACTION empty before we
  // start returning superblocks to the process heap.
  enum { EMPTY_FRACTION = SUPERBLOCK_FULLNESS_GROUP - 1 };

  // Reset value for the least-empty bin.  The last bin
  // (SUPERBLOCK_FULLNESS_GROUP-1) is for completely full superblocks,
  // so we use the next-to-last bin.
  enum { RESET_LEAST_EMPTY_BIN = SUPERBLOCK_FULLNESS_GROUP - 2 };

  // The number of empty superblocks that we allow any thread heap to
  // hold once the thread heap has fallen below 1/EMPTY_FRACTION
  // empty.
  enum { MAX_EMPTY_SUPERBLOCKS = EMPTY_FRACTION };

  // The maximum number of thread heaps we allow.  (NOT the maximum
  // number of threads -- Hoard imposes no such limit.)  This must be
  // a power of two! NB: This number is twice the maximum number of
  // PROCESSORS supported by Hoard.
  enum { MAX_HEAPS = 128 };

  // ANDing with this rounds to MAX_HEAPS.
  enum { MAX_HEAPS_MASK = MAX_HEAPS - 1 };

  //
  // The number of size classes.  This combined with the
  // SIZE_CLASS_BASE determine the maximum size of an object.
  //
  // NB: Once this is changed, you must execute maketable.cpp and put
  // the generated values into heap.cpp.
  enum { SIZE_CLASSES = 115 };

  // Every object is aligned so that it can always hold a double.
  enum { ALIGNMENT = sizeof(double) };

  // ANDing with this rounds to ALIGNMENT.
  enum { ALIGNMENT_MASK = ALIGNMENT - 1};

  // Used for sanity checking.
  enum { HEAP_MAGIC = 0x0badcafe };

  // Get the usage and allocated statistics.
  inline void getStats (int sizeclass, int& U, int& A);


#if HEAP_STATS
  // How much is the maximum ever in use for this size class?
  inline int maxInUse (int sizeclass);

  // How much is the maximum memory allocated for this size class?
  inline int maxAllocated (int sizeclass);
#endif

  // Insert a superblock into our list.
  void  insertSuperblock (int sizeclass,
             superblock * sb,
             processHeap * pHeap);

  // Remove the superblock with the most free space.
  superblock * removeMaxSuperblock (int sizeclass);

  // Find an available superblock (i.e., with some space in it).
  inline superblock * findAvailableSuperblock (int sizeclass,
                           block *& b,
                           processHeap * pHeap);

  // Lock this heap.
  inline void lock (void);

  // Unlock this heap.
  inline void unlock (void);

  // Set our index number (which heap we are).
  inline void setIndex (int i);

  // Get our index number (which heap we are).
  inline int getIndex (void);

  // Free a block into a superblock.
  // This is used by processHeap::free().
  // Returns 1 iff the superblock was munmapped.
  int freeBlock (block *& b,
         superblock *& sb,
         int sizeclass,
         processHeap * pHeap);

  //// Utility functions ////

  // Return the size class for a given size.
  inline static int sizeClass (const size_t sz);

  // Return the size corresponding to a given size class.
  inline static size_t sizeFromClass (const int sizeclass);

  // Return the release threshold corresponding to a given size class.
  inline static int getReleaseThreshold (const int sizeclass);

  // Return how many blocks of a given size class fit into a superblock.
  inline static int numBlocks (const int sizeclass);

  // Align a value.
  inline static size_t align (const size_t sz);

#ifdef CRYSTAL_HOARD
  // Return the class of superblock which holds blocks of the given size class
  inline static int superblockClass(const int sizeclass);

  inline static size_t superblockSizeFromClass(const int superblockClass);

  // release superblock if the reusableBlockLimit is reached
  bool unsbrkIfLimit(processHeap * pHeap, superblock * sb);

#endif

private:

  // Disable copying and assignment.

  hoardHeap (const hoardHeap&);
  const hoardHeap& operator= (const hoardHeap&);

  // Recycle a superblock.
  inline void recycle (superblock *);

  // Reuse a superblock (if one is available).
  inline superblock * reuse (int sizeclass);

  // Remove a particular superblock.
  void removeSuperblock (superblock *, int sizeclass);

  // Move a particular superblock from one bin to another.
  void moveSuperblock (superblock *,
               int sizeclass,
               int fromBin,
               int toBin);

  // Update memory in-use and allocated statistics.
  // (*UStats = just update U.)
  inline void incStats (int sizeclass, int updateU, int updateA);
  inline void incUStats (int sizeclass);

  inline void decStats (int sizeclass, int updateU, int updateA);
  inline void decUStats (int sizeclass);

  //// Members ////

#if HEAP_DEBUG
  // For sanity checking.
  const unsigned long _magic;
#else
  #define _magic HEAP_MAGIC
#endif

  // Heap statistics.
  heapStats    _stats[SIZE_CLASSES];

  // The per-heap lock.
#ifdef WIN32
  hoardLockTypeS _lock;
#else
  hoardLockType _lock;
#endif

  // Which heap this is (0 = the process (global) heap).
  int _index;

  // Reusable superblocks.
#ifndef CRYSTAL_HOARD
  superblock *    _reusableSuperblocks;
  int           _reusableSuperblocksCount;
#else
  superblock *  _reusableSuperblocks[SUPERBLOCK_CLASSES];
  int           _reusableSuperblocksCount[SUPERBLOCK_CLASSES];

  // The lookup table for superblock class size
  static size_t _superblockSize[SUPERBLOCK_CLASSES];

  // The lookup table for the limit of empty superblocks on the reusable list
  static int    _reusableSuperblockLimit[SUPERBLOCK_CLASSES];
#endif

  // Lists of superblocks.
  superblock *    _superblocks[SUPERBLOCK_FULLNESS_GROUP][SIZE_CLASSES];

  // The current least-empty superblock bin.
  int    _leastEmptyBin[SIZE_CLASSES];

  // The lookup table for size classes.
  static size_t    _sizeTable[SIZE_CLASSES];

  // The lookup table for release thresholds.
  static size_t    _threshold[SIZE_CLASSES];
};



void hoardHeap::incStats (int sizeclass, int updateU, int updateA) {
  assert (_magic == HEAP_MAGIC);
  assert (updateU >= 0);
  assert (updateA >= 0);
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);
  _stats[sizeclass].incStats (updateU, updateA);
}



void hoardHeap::incUStats (int sizeclass) {
  assert (_magic == HEAP_MAGIC);
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);
  _stats[sizeclass].incUStats ();
}


void hoardHeap::decStats (int sizeclass, int updateU, int updateA) {
  assert (_magic == HEAP_MAGIC);
  assert (updateU >= 0);
  assert (updateA >= 0);
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);
  _stats[sizeclass].decStats (updateU, updateA);
}


void hoardHeap::decUStats (int sizeclass)
{
  assert (_magic == HEAP_MAGIC);
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);
  _stats[sizeclass].decUStats();
}


void hoardHeap::getStats (int sizeclass, int& U, int& A) {
  assert (_magic == HEAP_MAGIC);
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);
  _stats[sizeclass].getStats (U, A);
}


#if HEAP_STATS
int hoardHeap::maxInUse (int sizeclass) {
  assert (_magic == HEAP_MAGIC);
  return _stats[sizeclass].getUmax();
}


int hoardHeap::maxAllocated (int sizeclass) {
  assert (_magic == HEAP_MAGIC);
  return _stats[sizeclass].getAmax();
}
#endif


superblock * hoardHeap::findAvailableSuperblock (int sizeclass,
                         block *& b,
                         processHeap * pHeap)
{
  assert (this);
  assert (_magic == HEAP_MAGIC);
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);

  superblock * sb = NULL;
  int reUsed = 0;

  // Look through the superblocks, starting with the almost-full ones
  // and going to the emptiest ones.  The Least Empty Bin for a
  // sizeclass is a conservative approximation (fixed after one
  // iteration) of the first bin that has superblocks in it, starting
  // with (surprise) the least-empty bin.

  for (int i = _leastEmptyBin[sizeclass]; i >= 0; i--) {
    sb = _superblocks[i][sizeclass];
    if (sb == NULL) {
      if (i == _leastEmptyBin[sizeclass]) {
    // There wasn't a superblock in this bin,
    // so we adjust the least empty bin.
    _leastEmptyBin[sizeclass]--;
      }
    } else {
      assert (sb->getOwner() == this);
      break;
    }
  }

#if 1
  if (sb == NULL) {
    // Try to reuse a superblock.
    sb = reuse (sizeclass);
    if (sb) {
      assert (sb->getOwner() == this);
      reUsed = 1;
    }
  }
#endif

  if (sb != NULL) {
    // Sanity checks:
    //   This superblock is 'valid'.
    assert (sb->isValid());
    //   This superblock has the right ownership.
    assert (sb->getOwner() == this);

    int oldFullness = sb->getFullness();

    // Now get a block from the superblock.
    // This superblock must have space available.
    b = sb->getBlock();
    assert (b != NULL);

    // Update the stats.
    incUStats (sizeclass);

    if (reUsed) {
      insertSuperblock (sizeclass, sb, pHeap);
      // Fix the stats (since insert will just have incremented them
      // by this amount).
      decStats (sizeclass,
        sb->getNumBlocks() - sb->getNumAvailable(),
        sb->getNumBlocks());
    } else {
      // If we've crossed a fullness group,
      // move the superblock.
      int fullness = sb->getFullness();

      if (fullness != oldFullness) {
    // Move the superblock.
    moveSuperblock (sb, sizeclass, oldFullness, fullness);
      }
    }
  }

  // Either we didn't find a superblock or we did and got a block.
  assert ((sb == NULL) || (b != NULL));
  // Either we didn't get a block or we did and we also got a superblock.
  assert ((b == NULL) || (sb != NULL));

  return sb;
}


int hoardHeap::sizeClass (const size_t sz) {
  // Find the size class for a given object size
  // (the smallest i such that _sizeTable[i] >= sz).
  int sizeclass = 0;
  while (_sizeTable[sizeclass] < sz)
    {
      sizeclass++;
      assert (sizeclass < SIZE_CLASSES);
    }
  return sizeclass;
}


size_t hoardHeap::sizeFromClass (const int sizeclass) {
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);
  return _sizeTable[sizeclass];
}


int hoardHeap::getReleaseThreshold (const int sizeclass) {
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);
  return _threshold[sizeclass];
}


int hoardHeap::numBlocks (const int sizeclass) {
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);
  const size_t s = sizeFromClass (sizeclass);
  assert (s > 0);
  const int blksize = align (sizeof(block) + s);
  // Compute the number of blocks that will go into this superblock.
#ifndef CRYSTAL_HOARD
  int nb = MAX (1, ((SUPERBLOCK_SIZE - sizeof(superblock)) / blksize));
#else
  int nb = 1;
  int sbClass = 0;
  while ( (sbClass < SUPERBLOCK_CLASSES) && nb == 1 )
  {
    nb = MAX(1, ((_superblockSize[sbClass] - sizeof(superblock)) / blksize));
    sbClass++;
  }
#endif
  return nb;
}


#ifdef CRYSTAL_HOARD
int hoardHeap::superblockClass(const int sizeclass)
{
  assert (sizeclass >= 0);
  assert (sizeclass < SIZE_CLASSES);
  const size_t s = sizeFromClass (sizeclass);
  assert (s > 0);
  const int blksize = align (sizeof(block) + s);

  int nb = 1;
  int sbClass = 0;
  do
  {
    nb = MAX(1, ((_superblockSize[sbClass] - sizeof(superblock)) / blksize));
  }
  while ( (nb == 1) && (++sbClass < SUPERBLOCK_CLASSES) );

  return sbClass;
}


size_t hoardHeap::superblockSizeFromClass(const int superblockClass)
{
  assert (superblockClass >= 0);
  assert (superblockClass < SUPERBLOCK_CLASSES);
  return _superblockSize[superblockClass];
}
#endif  // CRYSTAL_HOARD


void hoardHeap::lock (void)
{
  assert (_magic == HEAP_MAGIC);
  hoardLock (_lock);
}


void hoardHeap::unlock (void) {
  assert (_magic == HEAP_MAGIC);
  hoardUnlock (_lock);
}


size_t hoardHeap::align (const size_t sz)
{
  // Align sz up to the nearest multiple of ALIGNMENT.
  // This is much faster than using multiplication
  // and division.
  return (sz + ALIGNMENT_MASK) & ~ALIGNMENT_MASK;
}


void hoardHeap::setIndex (int i)
{
  _index = i;
}


int hoardHeap::getIndex (void)
{
  return _index;
}




void hoardHeap::recycle (superblock * sb)
{
  assert (sb != NULL);
  assert (sb->getOwner() == this);
  assert (sb->getNumBlocks() > 1);
  assert (sb->getNext() == NULL);
  assert (sb->getPrev() == NULL);
  assert (hoardHeap::numBlocks(sb->getBlockSizeClass()) > 1);

#ifndef CRYSTAL_HOARD
  sb->insertBefore (_reusableSuperblocks);
  _reusableSuperblocks = sb;
  ++_reusableSuperblocksCount;
#else
  int sbClass = sb->getSuperblockClass();
  assert (sbClass < SUPERBLOCK_CLASSES);
  sb->insertBefore( _reusableSuperblocks[sbClass] );
  _reusableSuperblocks[sbClass] = sb;
  ++_reusableSuperblocksCount[sbClass];
#endif
  // printf ("count: %d => %d\n", getIndex(), _reusableSuperblocksCount);
}


superblock * hoardHeap::reuse (int sizeclass)
{
  // Make sure that we aren't using a sizeclass
  // that is too big for a 'normal' superblock.
  if (hoardHeap::numBlocks(sizeclass) <= 1) {
    return NULL;
  }

#ifndef CRYSTAL_HOARD
  if (_reusableSuperblocks == NULL) {
    return NULL;
  }

  // Pop off a superblock from the reusable-superblock list.
  assert (_reusableSuperblocksCount > 0);
  superblock * sb = _reusableSuperblocks;
  _reusableSuperblocks = sb->getNext();
  sb->remove();
  assert (sb->getNumBlocks() > 1);
  --_reusableSuperblocksCount;
#else
  int sbClass = superblockClass(sizeclass);
  assert ( sbClass < SUPERBLOCK_CLASSES );

  // Check for reusable superblocks of this size class
  if (_reusableSuperblocks[sbClass] == NULL) {
    return NULL;
  }

  // Pop off a superblock from the reusable-superblock list.
  assert (_reusableSuperblocksCount[sbClass] > 0);
  superblock * sb = _reusableSuperblocks[sbClass];
  _reusableSuperblocks[sbClass] = sb->getNext();
  sb->remove();
  assert (sb->getNumBlocks() > 1);
  --_reusableSuperblocksCount[sbClass];
#endif  // CRYSTAL_HOARD

  // Reformat the superblock if necessary.
  if (sb->getBlockSizeClass() != sizeclass) {
    decStats (sb->getBlockSizeClass(),
          sb->getNumBlocks() - sb->getNumAvailable(),
          sb->getNumBlocks());

    sb = new ((char *) sb) superblock (numBlocks(sizeclass), sizeclass, this);

    incStats (sizeclass,
          sb->getNumBlocks() - sb->getNumAvailable(),
          sb->getNumBlocks());
  }

  assert (sb->getOwner() == this);
  assert (sb->getBlockSizeClass() == sizeclass);
  return sb;
}

#endif // _HEAP_H_